1. Field of the Invention
The present invention relates to the field of halftone image production. In particular, the present invention relates to an apparatus and a method for creating a dither matrix in a less compute-intensive manner for use in a color printing environment.
2. Description of Related Art
The use of halftone patterns is required whenever printing graphics with traditional inks upon paper. Halftone techniques arose because the continuously varying gradations of gray scale and colors cannot be directly printed by offset, dot-matrix, ink-jet, and other printer technologies that utilize the deposition of constant-shaded dots of black or colored ink. A common early halftone technique utilized a uniform screen, as shown in FIG. 1. The segment of uniform screen 10 includes many cells, of which cell 12 is exemplary. Changing the density of gray scale using the uniform screen 10 may be performed by enlarging or shrinking the size of the ink dot corresponding to each cell. A light gray may be shown by making the ink dots relatively small in size. Conversely, a darker gray may be shown by making the ink dots relatively larger. The ink dot placed at a cell may be of any shape, with the square dots shown in FIG. 1 merely serving as examples.
The uniform screen 10 may be extended to cover an entire image. This is a simple process of uniformly extending the existing screen pattern, and requires no more than simple geometric calculations. However, the uniform screen 10 of FIG. 1 has certain visual drawbacks. The human visual system (HVS) is very sensitive at recognizing unintentional patterns, called artifacts, caused by the use of a halftone pattern. The HVS is most sensitive to slowly-varying in space (xe2x80x9clow frequencyxe2x80x9d) artifacts and much less sensitive to rapidly-varying in space (xe2x80x9chigh frequencyxe2x80x9d) artifacts. The literature on the subject often characterizes the HVS as possessing a xe2x80x9clow-pass filterxe2x80x9d. Additionally, the HVS is much more sensitive to patterns falling on a horizontal or vertical line. In the FIG. 1 example, the cells line up along line 14. Line 14 forms an angle of xcex8 degrees from a horizontal line 16. It is well-known in the art that the HVS is least sensitive to artifacts when xcex8 is around 45 degrees.
A better approach is illustrated in the dither pattern of FIG. 2. The dither pattern 20 includes a large number of cells, of which a typical one is cell 22. There are more blank spaces between the dots of dither pattern 20 so this would correspond to a light gray. More dots could be added for a darker shade of gray. The cells of dither pattern 20 have been arranged so that repetitive patterns, recognizable by the HVS, are minimized. It would appear on first glance that such a useful dither pattern 20 is xe2x80x9crandomxe2x80x9d, but a truly random pattern would include clumps of cells and also empty spaces. Hence the dither pattern 20 would more correctly be described as evenly but not regularly patterned.
The dither pattern 20 of FIG. 2 corresponds to a particular percentage of cells being selected for ink-dot placement. In order to allow for differing percentages of cells being selected, a related dither matrix to dither pattern 20 may be created. A dither matrix is a dither pattern with an ordering scheme for including cells depending upon the ratio of ink dots filled cells to total cells required. For clarity, a dither matrix 30 is shown in FIG. 3a with a limited number of cells. In practice, a much larger number of cells would be defined and used in a dither matrix. To create dither matrix 30 from dither pattern 20, each cell such as exemplary cell 22 may have associated with it a threshold value, selected from a sequence from 1 through A, where A is the total number of cells in a dither pattern. For example, the threshold value stored in ordered cell 32 is the number 13. This means that if the ratio of dark cells to total cells is 13/A, then a proper pattern is for the printer to place ink dots at all ordered cells with a threshold value of 13 or less.
In order to extend the dither matrix 30 to cover an entire image, dither matrix 30 is replicated and applied as tiles. In FIG. 3b a typical tiling scheme is illustrated. A replicated copy matrix 40 of dither matrix 30 is placed at locations in a grid 42 covering the size of the image required.
A useful dither pattern such as dither pattern 20 is not easily created. One method of creating such a useful dither pattern, well-known in the art, is to use the technique known as error diffusion. In this method, first a two dimensional transfer function Vij that models the perceived responsiveness to patterns of the HVS is created. Vij is called a modulation transfer function (MTF). Then, a two dimensional function pij that describes the location of all the selected cells in a given dither pattern is defined. Finally, a cost function that approximates the amount of artifacts seen by a human, depending upon Vij and a given pij, is created. In one embodiment, the cost function Cost(pij) is given by Equation 1 below.                               Cost          ⁡                      (                          p              ij                        )                          =                              ∑                          i              =              1                        N                    ⁢                                    ∑                              j                =                1                            N                        ⁢                                          V                2                            ⁢              ijPijP              *              ij                                                          Equation        ⁢                  xe2x80x83                ⁢        1            
where Pij is the discrete Fourier transform (DFT) of the given pattern pij.
One method of selecting the least-objectionable pattern pij for use in a dither pattern is to evaluate the cost function for all such patterns pij, and then select one of the pij corresponding to the minimum value of the cost function. This is not practicable. The number of such possible combinations pij representing M cells selected in a dither pattern of N by N cells is (N2!)/M!(N2xe2x88x92M)!. This is an enormous number even for smaller dither patterns such as 32 by 32, and the number increases substantially for desired dither patterns of 256 by 256 or even 1024 by 1024 cells. Evaluating Equation 1 for such large numbers of candidate patterns is computationally intensive, and for all but the smallest sizes of dither patterns is impractical with reasonable amounts of computer resources.
An additional issue in printing colors with dither matrices, such as dither matrix 30, is that inks are transparent to varying degrees. If the same dither matrix were used for differing primary colors, such as cyan, magenta, and yellow, this would result in placing the different color""s ink dots roughly on top of one another. Light would then have to pass through multiple layers of ink to reflect off the base paper sheet. Having light pass through such multiple layers may produce unwanted multiple internal reflections and other similar optical effects that will yield impure colors when viewed.
A system and method for color printing is disclosed. In one embodiment, the method for color printing begins by printing a first primary color, usually cyan, with the aid of a previously generated dither matrix. The method continues by deriving a new dither matrix from the previously generated dither matrix by moving each position in the previously generated dither matrix a short random distance, thereby forming a corresponding position in the new dither matrix for printing another primary color, usually magenta. In an alternate embodiment, a new dither matrix is derived from the previously generated dither matrix by inverting the positions in the previously generated dither matrix to the positions of the new dither matrix. In other embodiments, additional dither matrices may be derived by a process of shifting the previously generated dither matrix horizontally or vertically and wrapping around the edges of the original dither matrix. Additional new dither matrices may be created in a similar manner for use in printing other primary colors or black.